package interview.bst2sdll;

public class BinarySearchTreeToSortedDoublyLinkedList {
	public void bstToSDLL(Node root) {
		Node[] ret = new Node[2];
		inOrderTraversal(root, ret);
		ret[0].setLeft(ret[1]);
		ret[1].setRight(ret[0]);
	}

	private void inOrderTraversal(Node root, Node[] ret) {
		if(root == null) {
			ret[0] = null;
			ret[1] = null;
		}

		Node head, tail;
		inOrderTraversal(root.getLeft(), ret);
		root.setLeft(ret[1]);
		if(ret[0] != null) {
			head = ret[0];
		} else {
			head = root;
		}
		inOrderTraversal(root.getRight(), ret);
		root.setRight(ret[0]);
		if(ret[1] != null) {
			tail = ret[1];
		} else {
			tail = root;
		}

		ret[0] = head;
		ret[1] = tail;
	}
}
